home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 422_02 / misc / rdc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-03-20  |  6.5 KB  |  220 lines
  1. /*
  2.  * Ross Data Compression
  3.  *
  4.  * This program implements a simple (and fast) Data Compression Scheme
  5.  * devised by Ed Ross, and published in the Oct/1992 'C' Users Journal.
  6.  *
  7.  * Compile command: cc rdc -fop
  8.  */
  9. #include <stdio.h>
  10.  
  11. #define    HASH_LEN    4096        /* Number of hash table entries */
  12. #define    BUFF_LEN    16384        /* Buffer length */
  13.  
  14. /*
  15.  * Ross Data Compression - Compress functions
  16.  *
  17.  * Compress input buffer -> output buffer and return length of output
  18.  * buffer. Negative length indicates that buffer could not be compressed
  19.  */
  20. int rdc_compress(inbuff, inbuff_len, outbuff)
  21.     unsigned char    *inbuff, *outbuff;
  22.     unsigned int    inbuff_len;
  23. {
  24.     unsigned char    *in_idx, *inbuff_end, *anchor, *pat_idx, *out_idx,
  25.                     *outbuff_end, *hash_tbl[HASH_LEN];
  26.     unsigned int    cnt, gap, c, hash, *ctrl_idx, ctrl_bits, ctrl_cnt;
  27.  
  28.     inbuff_end = (in_idx = inbuff) + inbuff_len;
  29.     ctrl_idx = (unsigned int *) outbuff;
  30.     ctrl_cnt = 0;
  31.  
  32.     out_idx = outbuff + sizeof(unsigned int);
  33.     outbuff_end = (inbuff_len - 48) + outbuff;
  34.  
  35.     /* Skip compression for small buffers */
  36.     if(inbuff_len <= 18) {
  37.         memcpy(outbuff, inbuff, inbuff_len);
  38.         return 0 - inbuff_len; }
  39.  
  40.     /* Scan through inbuff */
  41.     while(in_idx < inbuff_end) {
  42.         /* Make room for control bits & check for outbuff overflow */
  43.         if(ctrl_cnt++ == 16) {
  44.             *ctrl_idx = ctrl_bits;
  45.             ctrl_cnt = 1;
  46.             ctrl_idx = (unsigned int *) out_idx;
  47.             out_idx += 2;
  48.             if(out_idx > outbuff_end) {
  49.                 memcpy(outbuff, inbuff, inbuff_len);
  50.                 return 0 - inbuff_len; } }
  51.  
  52.         /* Look for RLE */
  53.         c = *(anchor = in_idx++);
  54.         while((in_idx < inbuff_end) && (*in_idx == c) && ((in_idx - anchor) < 4114))
  55.             ++in_idx;
  56.  
  57.         /* Store compression code if character is repeated 2 or more times */
  58.         if((cnt = in_idx - anchor) > 2) {
  59.             if(cnt <= 18) {            /* Short RLE */
  60.                 *out_idx++ = cnt - 3;
  61.                 *out_idx++ = c; }
  62.             else {                    /* Long RLE */
  63.                 *out_idx++ = ((cnt -= 19) & 0x0F) + 16;
  64.                 *out_idx++ = cnt >> 4;
  65.                 *out_idx++ = c; }
  66.             ctrl_bits = (ctrl_bits << 1) | 1;
  67.             continue; }
  68.  
  69.         /* Look for pattern if 2 or more character remain in input buffer */
  70.         in_idx = anchor;
  71.         if((inbuff_end - in_idx) > 2) {
  72.             /* Locate offset of possible pattern in sliding dictionary */
  73.             hash = ((((in_idx[0] & 15) << 8) | in_idx[1])
  74.                 ^ ((in_idx[0] >> 4) | (in_idx[2] << 4))) & (int)(HASH_LEN-1);
  75.             pat_idx = hash_tbl[hash];
  76.             hash_tbl[hash] = in_idx;
  77.  
  78.         /* Compare characters if we are within 4098 bytes */
  79.         if((gap = in_idx - pat_idx) <= 4098) {
  80.             while((in_idx < inbuff_end) && (pat_idx < anchor)
  81.               && (*pat_idx == *in_idx) && ((in_idx - anchor) < 271)) {
  82.                 ++in_idx;
  83.                 ++pat_idx; }
  84.             /* Store pattern of more than 2 characters */
  85.             if((cnt = in_idx - anchor) > 2) {
  86.                 gap -= 3;
  87.                 if(cnt <= 15) {            /* Short pattern */
  88.                     *out_idx++ = (cnt << 4) + (gap & 0x0F);
  89.                     *out_idx++ = gap >> 4; }
  90.                 else {                    /* Long pattern */
  91.                     *out_idx++ = (gap & 0x0F) + 32;
  92.                     *out_idx++ = gap >> 4;
  93.                     *out_idx++ = cnt - 16; }
  94.                 ctrl_bits = (ctrl_bits << 1) | 1;
  95.                 continue; } } }
  96.  
  97.         /* Can't compress this character - copy to outbuff */
  98.         *out_idx++ = c;
  99.         in_idx = ++anchor;
  100.         ctrl_bits <<= 1; }
  101.  
  102.     /* Save last batch of control bits */
  103.     ctrl_bits <<= (16 - ctrl_cnt);
  104.     *ctrl_idx = ctrl_bits;
  105.  
  106.     /* Return size of compressed buffer */
  107.     return out_idx - outbuff;
  108. }
  109.  
  110. /*
  111.  * Ross Data Compression - Decompress functions
  112.  *
  113.  * Expand input buffer -> output buffer and return length of output
  114.  * buffer.
  115.  */
  116. int rdc_decompress(inbuff, inbuff_len, outbuff)
  117.     unsigned char    *inbuff, *outbuff;
  118.     unsigned int    inbuff_len;
  119. {
  120.     unsigned int    ctrl_bits, ctrl_mask, cmd, cnt, ofs;
  121.     unsigned char    *inbuff_idx, *outbuff_idx, *inbuff_end;
  122.  
  123.     ctrl_mask = 0;
  124.     inbuff_end = (inbuff_idx = inbuff) + inbuff_len;
  125.     outbuff_idx = outbuff;
  126.  
  127.     /* Process each item in inbuff */
  128.     while(inbuff_idx < inbuff_end) {
  129.         /* Get new load of control bits if needed */
  130.         if(!(ctrl_mask >>= 1)) {
  131.             ctrl_bits = *(unsigned int *)inbuff_idx;
  132.             inbuff_idx += 2;
  133.             ctrl_mask = 0x8000; }
  134.  
  135.         /* Just copy this character is control bit is zero */
  136.         if(!(ctrl_bits & ctrl_mask)) {
  137.             *outbuff_idx++ = *inbuff_idx++;
  138.             continue; }
  139.  
  140.     /* Undo the compression code */
  141.     cnt = (*inbuff_idx & 0x0f) + 3;
  142.     switch(cmd = (*inbuff_idx++ >> 4) & 0x0f) {
  143.         case 0 :        /* Short RLE */
  144.             memset(outbuff_idx, *inbuff_idx++, cnt);
  145.             outbuff_idx += cnt;
  146.             break;
  147.         case 1 :        /* Long RLE */
  148.             cnt += (*inbuff_idx++ << 4) + 16;
  149.             memset(outbuff_idx, *inbuff_idx++, cnt);
  150.             outbuff_idx += cnt;
  151.             break;
  152.         case 2 :        /* Long pattern */
  153.             ofs = (*inbuff_idx++ << 4) + cnt;
  154.             memcpy(outbuff_idx, outbuff_idx - ofs, cnt = *inbuff_idx ++ + 16);
  155.             outbuff_idx += cnt;
  156.             break;
  157.         default :        /* Short pattern */
  158.             ofs = (*inbuff_idx++ << 4) + cnt;
  159.             memcpy(outbuff_idx, outbuff_idx - ofs, cmd);
  160.             outbuff_idx += cmd; } }
  161.  
  162.     /* Return length of decompressed buffer */
  163.     return outbuff_idx - outbuff;
  164. }
  165.  
  166. /*
  167.  * Test program
  168.  */
  169. main(argc, argv)
  170.     int argc;
  171.     char *argv[];
  172. {
  173.     int isize, csize;
  174.     unsigned char inbuff[BUFF_LEN], outbuff[BUFF_LEN];
  175.  
  176.     FILE *fpi, *fpo;
  177.  
  178.     switch((argc == 4) ? toupper(*argv[1]) : 0) {
  179.         case 'C' :        /* Compress infile to outfile */
  180.             fpi = fopen(argv[2], "rvqb");
  181.             fpo = fopen(argv[3], "wvqb");
  182.             while(isize = fread(inbuff, BUFF_LEN, fpi)) {
  183.                 csize = rdc_compress(inbuff, isize, outbuff);
  184.                 if(fwrite(&csize, sizeof(int), fpo) != sizeof(int))
  185.                     abort("Can't write size");
  186.                 if(csize < 0)
  187.                     csize = 0 - csize;
  188.                 if(fwrite(outbuff, csize, fpo) != csize)
  189.                     abort("Can't write buffer"); }
  190.             if(fwrite(&isize, sizeof(int), fpo) != sizeof(int))
  191.                 abort("Can't write END flag");
  192.             fclose(fpi);
  193.             fclose(fpo);
  194.             break;
  195.         case 'D' :        /* Decompress infile to outfile */
  196.             fpi = fopen(argv[2], "rvqb");
  197.             fpo = fopen(argv[3], "wvqb");
  198.             for(;;) {
  199.                 if(fread(&isize, sizeof(int), fpi) != sizeof(int))
  200.                     abort("Can't read size");
  201.                 if(!isize)
  202.                     break;
  203.                 if(isize < 0) {    /* Uncompressed block - pass through */
  204.                     csize = 0 - isize;
  205.                     if(fread(outbuff, csize, fpi) != csize)
  206.                         abort("Can't read ublock"); }
  207.                 else {            /* Compressed block - decompress */
  208.                     if(fread(inbuff, isize, fpi) != isize)
  209.                         abort("Can't read cblock");
  210.                     csize = rdc_decompress(inbuff, isize, outbuff); }
  211.                 if(fwrite(outbuff, csize, fpo) != csize)
  212.                     abort("Can't write output file"); }
  213.             fclose(fpi);
  214.             fclose(fpo);
  215.             break;
  216.         default:
  217.             abort("\nUse: rdc Compress|Decompress <infile> <outfile>\n"); }
  218.  
  219. }
  220.